/**
 * https://leetcode.cn/submissions/detail/585451665/
 * 1377. T 秒后青蛙的位置
 * Hard, 黄伟杰 2024.12.06
 * DFS
 */

class Solution
{
public:
    double frogPosition(int n, vector<vector<int>> &edges, int t, int target)
    {
        vector<vector<int>> g(n + 1);
        g[1] = {0};
        for (auto e : edges)
        {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]); // 建图
        }
        double ans = 0;
        auto dfs = [&](auto dfs, int x, int fa, int tt, long long p) -> bool
        {
            if (x == target && (tt == 0 || g[x].size() == 1)) // 到达或者是叶子，tt是剩余秒数
            {
                ans = 1.0 / p;
                return true;
            }
            if (x == target || tt == 0)
                return false;
            for (int y : g[x])
                if (y != fa && dfs(dfs, y, x, tt - 1, p * (g[x].size() - 1)))
                    return true;
            return false;
        };
        dfs(dfs, 1, 0, t, 1);
        return ans;
    }
};